IP Addressing
Two network addressing schemes are currently deployed on the Internet. Internet Protocol version 4 (“IPv4”) is by far the most widely deployed Internet protocol (the other addressing scheme is “IPv6”). An IPv4 address (hereinafter referred to as an “IP address”) is a 32-bit integer, expressed as four 8-bit integers separated by period or “dot” characters. This is also known as “dotted-quad notation”. An example IP address in dotted-quad notation is 192.168.0.1. An IP address expressed in a dotted-quad notation may be translated to a binary representation for use within computers. For example, the integer 192 may be expressed in binary as 11000000, 168 as 10101000, 0 as 00000000, and 1 as 00000001. Thus, this translation is isomorphic with exactly one dotted-quad expression for each binary expression. While embodiments of the invention are described herein with respect to IPv4, the described embodiments may similarly process IPv6 addresses (128 bits) with little or no change to the described embodiments, as will be well understood by those of skill in the art after reading this disclosure.
Routing traffic on the Internet may involve determining the next “hop” (device) on the Internet to which a packet should be sent by inspecting the IP address of a packet. An IP address of a packet may be separated into a “network” segment and a “host” segment. For example, there is a prefix portion of an IP address that is considered to identify a specific network, while the remainder of the IP address identifies a host within that network. Therefore, when a device attempts to contact some other device on a different network, instead of keeping an entire list of IP addresses, the sending device only needs to keep a list of addresses identifying the networks it knows how to reach as well as a default address for handling all unknown destinations, and then sends the packet on its way. This reduces the size of the routing table that is used for routing packets within the Internet. As such, end-nodes on the Internet only need to know their own network prefix, and a “default” route to which traffic may be sent.
Originally, the network prefixing scheme was implicit depending on the first octet of an IP address. For certain values of the first octet, the network prefix was assumed to be 8 bits, meaning 24 bits would remain for the host; for another range of values of the first octet, the division was at 16 bits; for the remainder, the division was at 24 bits. These were known as Class A, Class B and Class C networks, respectively. However, this network prefixing scheme is too limiting. For example, a Class C network includes 256 addresses that is too small for many businesses, while a Class B network includes 65,536 addresses leading to address space waste.
In 1993, the Internet Engineering Task Force (IETF) proposed a new method of network prefixing allowing the partitioning to happen anywhere in an IP address. This is known as CIDR (“Classless Internet Domain Routing”). Using CIDR, the network prefix may be expressed in two different manners: (1) a first IP address followed by a second IP address, separated by a slash (“/”) character, e.g., 192.168.0.0/255.255.0.0; (2) an IP address followed by an integer from 1 to 31, separated by a slash (“/”) character, e.g., 192.168.0.0/16. In both cases, the data after the slash character indicates the number of bits in an IP address that define the network prefix. In the former case, the binary expression of the second IP address has bits “on” (or 1) if they are network bits, and “off” (or 0) if they are host bits. In the latter case, the integer specifies the number of bits that comprise the network prefix. For example: 192.168.0.0/255.255.0.0 and 192.168.0.0/16 both identify the same network that has a network prefix of 16 bits.
Using CIDR, smaller (or larger) blocks of IP addresses may be allocated to various networks or sub-networks as desired by placing the partition point anywhere in an IP address space that has been already assigned. For example, if a corporation is assigned a network that has a network prefix of 24 bits (and thus 8 host bits) such as 10.231.13.0/24, one or more sub-networks such as 10.231.13.0/25 and 10.231.13.128/25 may be created within the original network. An external entity that attempts to route a packet destined for a particular host in the organization may only need to route the packet to an initial router configured for that organization, and that router knows how to route the packet among the internal sub-networks.
Compressing a list of IP addresses to a relatively smaller list of CIDR expressions may involve identifying one or more common bits within the list of IP addresses and extrapolating one or more CIDR expressions that cover all members of the list of IP addresses. For example, consider a set of 256 IP addresses from 192.168.0.0 through 192.168.0.255. This entire list of IP addresses may be expressed using a single CIDR notation “192.168.0.0/24” as the first 24 bits of all of those IP addresses are identical. Such CIDR expressions may also include one or more additional IP addresses that are not members of the list of IP addresses. This extra “coverage” or “over-coverage” may be acceptable if it is determined that the extra hosts (addresses) covered by the one or more CIDR expressions may become hostile or the punishment of such additional hosts may be acceptable collateral for an organization to defend itself.
Binary Tree
In computer programming, a “tree” is a data structure comprising a set of objects called “nodes” that are linked in a tree-like pattern. Nodes may have arbitrary data stored within them. A tree may include a “root” indicating a starting point for the tree and one or more other nodes. Each node of a tree may have one or more other nodes associated with it as either “parents”, “siblings” or “children”. The “root” node of a tree has no parent, and a “leaf” node of a tree has no children. Two nodes of a tree with the same parent are considered to be siblings. A connection between a parent node and its children nodes is called a “branch” or a “link”. A tree with no more than two children per node is called a “binary” tree. In a binary tree, the children (if they are exist) of a node may be referred to as “left” and “right” of that node. Following a link from a node to one of its children is called “descending”.
Trees may be used for data sorting. For example, a well-known technique called “depth-first search” may be used to sort a list of words by generating a tree using the list of words. This may be done in the following manner:                Staring with the first word in the set of words, create a root node and store that first word in the root node;        For each subsequent word to be inserted into the tree, start at the root node, and compare the word to be inserted with the word currently in the node.        If the word to be inserted is lexically (i.e., in dictionary order) before the word currently in the node and there is no “left” child for the node, create a left child of the current node and insert the word there. Otherwise, if the word being inserted is lexically before the word in the node and there is a left child for the node, descend to the left and repeat the test until the appropriate insertion point is determined.        If the word being inserted is lexically after the word in the node and there is no right child for the node, create a right child of the current node and insert the word there. Otherwise, if the word being inserted is lexically after the word in the node and there is no right child, descend to the right and repeat the test until the appropriate insertion point is found.        
Upon completion of all the insertions for all the words in the list, a binary tree is generated with the leaf nodes in left-to-right order containing a sorted list of the original words.
Since an IP address is a unique sequence of ones and zeros, the IP address may be represented as a unique sequence of “left” and “right” descents in a binary tree.
Related Problems
A firewall is a piece of software or hardware deployed at an organization to protect the organization from external attacks. A firewall may analyze each incoming packet and make “allow” or “deny” decisions based upon one or more user-configurable rules. The one or more user-configurable rules may be based upon one or more IP addresses that appear to be participating in an attack. For example, a rule may be configured that causes the firewall to block all traffic originated from a particular IP address that appears to be participating in an attack. However, the number of user-configurable rules that the firewall needs to compare for each incoming packet may impact the performance of the firewall. The more rules are added to the firewall configuration, the slower the firewall performance would be as each rule is consulted for every arriving packet. An attack involving a large number of IP addresses may cause a large number of rules to be added to the configuration, which in turn causes a large number of rules to be applied for each incoming packet, thereby slowing down the firewall's performance.
An optimization of the above problem and similar problems for various network applications and tools (e.g., routers, firewalls, network monitoring tools, and others) is desirable.